동적 프로그래밍_(비교)

=== 최적제어에서의 동적 프로그래밍 ===

기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 [math(x(t))]와 현재의 입력 [math(u(t))]을 기반으로 계산되는 비용 [math(J(t))]을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 핵심 개념을 제시하는데 이것이 바로 '''최적성의 원리'''이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다. 때문에 동적 프로그래밍은 문제를 전체적으로 한 번에 푸는 것이 아니라, 문제를 시간적으로 나누어 각 시점마다 최적의 결정을 순차적으로 내려가는 방식으로 접근한다.

=== 컴퓨터 과학에서의 동적 프로그래밍 ===

이와 관련된 대표적인 예제는 동적 프로그래밍의 방법을 적용하여 피보나치 수열을 최적화 하는 문제가 있다. 아래의 코드는 Dictionary<int, int[]> 형태의 자료구조에 계산 값을 저장한 뒤, 중복된 계산식이 호출되면 해당 자료구조에서 이전에 계산된 값을 확인 후, 계산 값을 반환하여 불필요한 계산~~삽질~~을 처리하지 않게 한다.

{{{#!syntax cpp